
//3048.标记所有下标的最早秒数I
class Solution {
    //检查时间为t时，是否满足条件
    bool check(vector<int>& nums,vector<int>& changeIndices,int t)
    {
        int n=nums.size();
        vector<int> last_n(n,-1);
        for(int i=0;i<t;i++)
            last_n[changeIndices[i]-1]=i;  //存储各个科目最后一次考试时间
        if(ranges::find(last_n,-1)!=last_n.end()) return false;   //存在没有考试时间的科目

         int have=0;
        //i表示时间,changeIndices[i]-1是第几门科目,nums[changeIndices[i]-1]是该门复习需要的时间
        for(int i=0;i<t;i++)
        {
            if(i==last_n[changeIndices[i]-1])
            {
                if(have<nums[changeIndices[i]-1]) return false;
                else have-=nums[changeIndices[i]-1];
            }
            else have++;
        }
        return true;         
    }

public:
    int earliestSecondToMarkIndices(vector<int>& nums, vector<int>& changeIndices) {
        int n=nums.size(),m=changeIndices.size();
        if(n>m) return -1;

        int left=n-1,right=m+1;  //不能确定时间为m时是否满足条件，但是m+1是一定不满足条件的所以将right置为m+1
        while(left+1<right)
        {
            int mid=left+(right-left)/2;
            if(check(nums,changeIndices,mid)) right=mid;
            else left=mid;
        }
        return right>m?-1:right;
    }
};